import java.util.*;

public class Demo13 {

    public static void main(String[] args) {
        /*int[] arr = {6,4,8,5,2,7};
        int[][] arr1 = {{0,1},{0,3},{2,4},{3,4},{2,2}};
        leftmostBuildingQueries(arr,arr1);*/


//        System.out.println(minimumSteps("111111111100100010"));

    }

/*    public static long minimumSteps(String s) {
        int len = s.length();
        int len1 = 0;
        int ret = 0;
        for(int i=0;i<len;i++){
            if (s.charAt(i) == '0'){
                ret += len1;
            }else{
                len1++;
            }
        }


        return ret;
    }*/

/*    public static long minimumSteps(String s) {
        long re = 0;
        int a = 0;
        for (char c : s.toCharArray()) {
            if (c=='0') re += a;
            else a++;
        }
        return re;
    }*/

 /*   public static int[] leftmostBuildingQueries(int[] heights, int[][] queries) {
        int n = heights.length;
        int q = queries.length;
        int[] ans = new int[q];
        for(int i=0;i<q;i++){
            int a = queries[i][0];
            int b = queries[i][1];
            if (a==b){
                ans[i] = a;
                continue;
            }
            if(a>b && heights[a]>heights[b]){
                ans[i] = a;
            }
            if(a<b && heights[a]<heights[b]){
                ans[i] = b;
            }
            int max = Math.max(a,b);
            int flag = 0;
            for(int j = max;j<n;j++){
                if (heights[j]>heights[a] && heights[j]>heights[b]){
                    flag = 1;
                    ans[i]=j;
                    break;
                }
            }
            if (flag==0){
                ans[i]=-1;
            }



        }
        return ans;


    }
*/

        public static int[] leftmostBuildingQueries(int[] heights, int[][] queries) {
        int n = heights.length;
        int q = queries.length;
        int[] ans = new int[q];
        for(int i=0;i<q;i++){
            int a = queries[i][0];
            int b = queries[i][1];
            if (a>b){
                int tmp = a;
                a = b;
                b = tmp;
            }
            if (heights[b]>=heights[a]){
                ans[i] = b;
                continue;
            }

            int flag = 0;
            for(int j = b;j<n;j++){
                if (heights[j] > heights[a] && heights[j]>heights[b]){
                    ans[i] = j;
                    flag = 1;
                    break;
                }
            }
            if (flag==0){
                ans[i] = -1;
            }


        }
        return ans;


    }














/*    public static void main(String[] args) {

        System.out.println(maximumXorProduct(53449611838892L,712958946092406L, 6));

    }


    public static int maximumXorProduct(long a, long b, int n) {
        long mod = 1000000007L;
        long area = 1L;
        for(int i = 0;i<n;i++){
            area *= 2;
        }

        long max = -1L;
        for(long i = 0;i<area;i++){
//            long tmp = ((a%mod^i)%mod)*((b%mod^i)%mod)%mod;
            long a1 = (a^i)%mod;
            long b1 = (b^i)%mod;
            long tmp = a1*b1;
            max = Math.max(max,tmp);
        }
        return (int)max;



    }*/









    /*public static void main(String[] args) {
        System.out.println(minimumSteps("111111111100100010"));
    }

    public static long minimumSteps(String s) {
        char[] str = s.toCharArray();
        long count = 0;
        for(int i = 1;i<str.length;i++){
            for(int j = 0;j<str.length-1;j++){
                if (str[j]>str[j+1]){
                    char tmp = str[j];
                    str[j] = str[j+1];
                    str[j+1] = tmp;
                    count++;
                }
            }

        }
        return count;



    }*/



/*    public int findMinimumOperations(String s1, String s2, String s3) {

        int n1 = 0;
        int n2 = 0;
        int n3 = 0;
        if (!(s1.charAt(0) == s2.charAt(0) && s2.charAt(0) == s3.charAt(0)) ){
            return -1;
        }

        int len1 = s1.length();
        int len2 = s2.length();
        int len3 = s3.length();
        int min = Math.min(len1,Math.min(len2,len3));
        int count = 0;
        for(int i = 0;i<min;i++){
            if (s1.charAt(i) == s2.charAt(i) && s2.charAt(i) == s3.charAt(i)){
                count++;
            }else{
                break;
            }
        }
        int ret = len1-count+len2-count+len3-count;
        return ret;


    }*/














/*    public int getValue(int[] gifts, int n) {
        Arrays.sort(gifts);
        int count = 0;
        for(int i = 0;i<n;i++){
            if (gifts[i] == gifts[n/2]){
                count++;
            }
        }
        if (count>gifts.length/2){
            return gifts[gifts.length/2];
        }

        return 0;
    }*/



/*    public static void main(String[] args) {
//        Scanner in = new Scanner(System.in);
//        // 注意 hasNext 和 hasNextLine 的区别
//        while (in.hasNextInt()) { // 注意 while 处理多个 case
//            int n = in.nextInt();
//            int a = in.nextInt();
//                int[] arr = new int[n];
//                for(int i = 0;i<n;i++){
//                    arr[i] = in.nextInt();
//                }
//
//                for(int i = 0;i<n;i++){
//                    if (a>=arr[i]){
//                        a+=arr[i];
//                    }else{
//                        a+=fun(arr[i], a);
//                    }
//                }
//                System.out.println(a);
//
//            }
//


        System.out.println(fun(615, 1997));

    }

    private static int fun(int a, int b) {
        int tmp = b%a;
        while (b%a!=0) {
            tmp = b%a;
            b=a;

        }
        return tmp;


    }*/








/*    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String str = in.nextLine();
            int[] arr = new int[128];
            for(int i = 0;i<str.length();i++){
                arr[str.charAt(i)]++;
            }
            int flag = 0;
            for(int i = 0;i<str.length();i++){
                if (arr[str.length()]==1){
                    System.out.println(str.charAt(i));
                    flag = 1;
                    break;
                }
            }
            if (flag==0){
                System.out.println(-1);
            }


        }
    }*/

/*
    public static int maximumStrongPairXor(int[] nums) {
        int max = Integer.MIN_VALUE;
        if(nums.length==1){
            return 0;
        }
        Arrays.sort(nums);

        for(int i = nums.length-1;i>0;i--){
            for(int j = i-1;j>0;j--){
                if (nums[i]-nums[j] <= nums[j]){
                    max = Math.max(max,nums[i]^nums[j]);
                }
            }

        }


        return max;

    }
*/



/*    public static void main(String[] args) {
//        int[] arr =  {1,2,3,4,5};
//        System.out.println(maximumStrongPairXor(arr));
        List<List<String>> arr = new ArrayList<>();
//       ,,,,};
        arr.add(Arrays.asList(new String[]{"a", "0549"}));
        arr.add(Arrays.asList(new String[]{"b","0457"}));
        arr.add(Arrays.asList(new String[]{"a","0532"}));
        arr.add(Arrays.asList(new String[]{"a","0621"}));
        arr.add(Arrays.asList(new String[]{"b","0540"}));



        System.out.println(findHighAccessEmployees(arr));

    }


    public static List<String> findHighAccessEmployees(List<List<String>> access_times) {

        HashMap<String, List<String>> hash = new HashMap<>();
        int n = access_times.size();
        List<String> ret = new ArrayList<>();
        for(int i = 0;i<n;i++){
            if (!hash.containsKey(access_times.get(i).get(0))){
                List<String> tmp = new ArrayList<>();
                tmp.add(access_times.get(i).get(1));
                hash.put(access_times.get(i).get(0),tmp);
            }else{
                List<String> tmp = hash.get(access_times.get(i).get(0));
                tmp.add(access_times.get(i).get(1));
                hash.put(access_times.get(i).get(0),tmp);
            }
        }

        //将hash表中的value排序
        Iterator<String> iterator = hash.keySet().iterator();
        while (iterator.hasNext()){
            String key = iterator.next();
            Collections.sort(hash.get(key));

//            System.out.println(hash.get(key));
            //这里可以顺便判断当前key是否在一小时内三次访问，相邻三个数之间的最大差值小于100
            if(hash.get(key).size()>=3){
                for(int i = 0;i<hash.get(key).size()-2;i++){
                    if (Integer.parseInt(hash.get(key).get(i))+99 >= Integer.parseInt(hash.get(key).get(i+2))){
                        ret.add(key);
                        break;
//                        System.out.println(Integer.parseInt(hash.get(key).get(i))+99 );
//                        System.out.println(Integer.parseInt(hash.get(key).get(i+2)) );
//                        System.out.println(ret);
                    }
                }
            }

        }

        //判断是否有一小时三次访问

        return ret;
    }*/

   /* public static int maximumStrongPairXor(int[] nums) {
        int max = Integer.MIN_VALUE;

        for(int left = 0;left<nums.length;left++){
            for(int right = 0;right < nums.length; right++){
                if (nums[left]>nums[right]){
                    if (nums[left]-nums[right] <= Math.min(nums[left],nums[right])){
                        max = Math.max(max,nums[left]^nums[right]);
                    }
                }else{
                    if (nums[right]-nums[left] <= Math.min(nums[left],nums[right])){
                        max = Math.max(max,nums[left]^nums[right]);
                    }
                }
            }

        }
        return max;

    }
*/


   /* public static void main(String[] args) {
        int[][] arr= {{8,5,2},{6,4,1},{9,7,3}};
        System.out.println(maxSpending(arr));
    }

    public static long maxSpending(int[][] values) {

        int m = values.length;
        int n = values[0].length;
        int[] index = new int[m];
        for(int i = 0;i<m;i++){
            index[i] = n-1;
        }
        long sum = 0;
        for(int i = 1;i<=m*n;i++){
            int min = minNum(values,index);
            sum += i*min;
        }
        return sum;

    }

    private static int minNum(int[][] values, int[] index) {
        int min = Integer.MAX_VALUE;
        int dm = 0;
        for(int i = 0;i<values.length;i++){
            if (index[i]>=0 && min>values[i][index[i]]){
                min = values[i][index[i]];
                dm = i;
            }

        }
        index[dm]--;
        return min;
    }
*/


/*
    public static void main(String[] args) {
//        System.out.println(stringCount(4));

        System.out.println(stringCount(10));
//        System.out.println(modecount());
    }

    public static long stringCount(int n) {
        long sum = 1;
        for(int i = 0;i<n-4;i++){
           sum = sum*26;
        }
        System.out.println(sum);
        sum=sum*12;

        sum =sum* jiec(n,4);

        return sum;

    }

    private static long jiec(int n, int k) {
        //n的阶乘
        long ret = 1;
        for(int i = 5;i<=n;i++){
            ret = ret*i;
        }
        System.out.println(ret);
        return ret;

    }*/
    // 526083947580

   /* public static long stringCount1(int n) {
        long sum = 1;
        for(int i = 0;i<n-4;i++){
            sum = ((sum%modecount())*26)%modecount();
        }
        sum=sum%modecount()*12;

        sum =((sum%modecount())* jiec(n,4))%modecount();

        return (sum%modecount());

    }

    private static int jiec1(int n, int k) {
        //n的阶乘
        long ret = 1;
        for(int i = 5;i<=n;i++){
            ret = (ret%modecount())*(i%modecount());
        }
        return (int)ret;

    }*/

    private static long modecount() {
        long ret = 1;
        for(int i = 0;i<10;i++){
            ret = ret*10;
        }
        return ret+7;
    }

/*    public static int distributeCandies(int n, int limit) {
        int count = 0;
        for(int i = 0;i<=limit;i++){
            for(int j = 0;j<=limit-i;j++){
                for(int k = 0;k<=limit-i-j;k++){
                    if (i+j+k==n){
                        count++;
                    }
                }
            }

        }
        return count;
    }*/


  /*  public static long distributeCandies(int n, int limit) {
        long count = 0;
        for(int i = 0;i<=limit;i++){
            for(int j = 0;j<=limit-i;j++){
                for(int k = 0;k<=limit-i-j;k++){
                    if (i+j+k==n){
                        count++;
                    }
                }
            }

        }
        return count;
    }

*/




/*
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        while (t>0){
            t--;
            int n = in.nextInt();
            int k = in.nextInt();
            int[] arr = new int[2*n];
            for(int i = 0;i<2*n;i++){
                arr[i] = in.nextInt();
            }
            Stack<Integer> mid = new Stack<>();
            Stack<Integer> left = new Stack<>();
            Stack<Integer> right = new Stack<>();
            for(int i = arr.length-1;i>=0;i--){
                mid.push(arr[i]);
            }
            while (k>0){
                k--;
                for(int i = 0;i<n;i++){
                    left.push(mid.pop());
                }
                for(int i = 0;i<n;i++){
                    right.push(mid.pop());
                }
                for(int i = 0;i<n;i++){
                    mid.push(right.pop());
                    mid.push(left.pop());
                }
            }
            while (!mid.isEmpty()){
                System.out.print(mid.pop()+" ");
            }



        }
    }
*/







/*    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()){
            String n = in.nextLine();
            String str = in.nextLine();
            mouseMove(Integer.parseInt(n),str);
        }


    }

    public static void mouseMove(int n,String orderStr){
        char[] order = orderStr.toCharArray();

        //当前光标所在位置
        int mouse = 1;
        //显示列表第一首位置的歌曲
        int first = 1;
        //指令处理
        if (n<=4){
            //循环处理每一个指令
            for(int i = 0;i<order.length;i++){
                if (mouse == 1 && order[i] == 'U'){
                    mouse = n;
                }else if (mouse == n && order[i] == 'D'){
                    mouse = 1;
                }else if (order[i] == 'U'){
                    mouse--;
                }else if(order[i] == 'D'){
                    mouse++;
                }
            }
            for(int i = 1;i<n;i++){
                System.out.print(i+" ");
            }
            System.out.println(n);
            System.out.println(mouse);

        }else{
            for(int i = 0;i<order.length;++i){
                if (first==1 && mouse==1 && order[i]=='U'){
                    first = n-3;
                    mouse = n;
                }else if(first == n-3 && mouse==n && order[i] == 'D'){
                    first = 1;
                    mouse = 1;
                }else if(first!=1 && first == mouse && order[i] == 'U'){
                    first--;
                    mouse--;
                }else if(first!=n-3 && first+3 == mouse && order[i] == 'D'){
                    first++;
                    mouse++;
                }else if(order[i] == 'U'){
                    mouse--;
                }else if(order[i] == 'D'){
                    mouse++;
                }
            }
            for(int i= first; i < first+3;i++){
                System.out.print(i+" ");
            }
            System.out.println(first+3);
            System.out.println(mouse);

        }


    }*/







/*    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String str1 = in.nextLine();
            String str2 = in.nextLine();

            int len1 = str1.length();
            int len2 = str2.length();
            int[][] dp = new int[len1+1][len2+1];
            int max = 0;
            for(int i = 1;i<=len1;i++){
                for(int j = 1;j<=len2;j++){
                    if (str1.charAt(i-1)==str2.charAt(j-1)){
                        dp[i][j] = dp[i-1][j-1]+1;
                        max = Math.max(max, dp[i][j]);
                    }
                }
            }
            System.out.println(max);


        }
    }*/




    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String str = in.nextLine();
            int left = 0;
            int right = str.length()-1;
            char[] arr = str.toCharArray();
            while (left<right){
                char tmp = arr[left];
                arr[left] = arr[right];
                arr[right] = tmp;
                left++;
                right--;
            }
            System.out.println(arr);



        }
    }*/




/*
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String str1 = in.nextLine();
            String str2 = in.nextLine();
            int len1 = str1.length();
            int len2 = str2.length();
            int[][] dp = new int[len1+1][len2+1];
            int max = 0;
            for(int i = 1;i<=len1;i++){
                for(int j = 1; j <= len2;j++){
                    if (str1.charAt(i-1)==str2.charAt(j-1)){
                        dp[i][j] = dp[i-1][j-1]+1;
                    }else{
                        dp[i][j] = 0;
                    }
                    max =Math.max(max,dp[i][j]);
                }
            }


            if (len1>len2){
                for(int i=1;i<=len1;i++){
                    int flag = 0;
                    for(int j = 1;j<=len2;j++){
                        if (max==dp[i][j]){
                            int len = i-max;
                            System.out.println(str1.substring(len, i));
                            flag = 1;
                            break;
                        }
                    }
                    if (flag==1){
                        break;
                    }

                }
            }else{
                for(int i=1;i<=len2;i++){
                    int flag = 0;
                    for(int j = 1;j<=len1;j++){
                        if (max==dp[j][i]){
                            int len = j-max;
                            System.out.println(str1.substring(len, j));
                            flag = 1;
                            break;
                        }
                    }
                    if (flag==1){
                        break;
                    }

                }
            }





        }
    }
*/







/*    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            if (n == 0){
                break;
            }
            int count = 0;
            while (n>1){
                if (n==2){
                    count++;
                    break;
                }else{
                    count += n/3;
                    n = n/3+n%3;
                }
            }
            System.out.println(count);





        }
    }*/










/*

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String t = in.nextLine();
            String s = in.nextLine();
            System.out.println(match(t,s));
        }
    }

    public static boolean match(String t,String s){
        char[] ct = t.toCharArray();
        char[] cs = s.toCharArray();
        int lt = ct.length;
        int ls = cs.length;
        boolean[][] dp = new boolean[ls+1][lt+1];
        dp[0][0] = true;
        for(int i = 0;i<=ls;i++){
            for(int j=1;j<=lt;j++){
                if (ct[j-1]=='*'){
                    if (i==0){
                        dp[i][j]=dp[i][j-1];
                    }else{
                        if (cs[i-1]=='.' || (cs[i-1]>='A' && cs[i-1]<='Z') ||
                                (cs[i-1]>='a' && cs[i-1]<='z') ||
                                (cs[i-1]>='0' && cs[i-1]<='9')){
                            dp[i][j]=dp[i-1][j]||dp[i][j-1];
                        }
                    }
                }else{
                    if (i>0 && defs(ct[j-1],cs[i-1])){
                        dp[i][j] = dp[i-1][j-1];
                    }

                }
            }
        }
        return dp[ls][lt];

    }

    private static boolean defs(char t, char s) {
        if (t == '?') {
            return true;
        }
        if (t>='a' && t<='z'){
            t=(char)(t-'a'+'A');
        }
        if (s>='a'&&s<='z'){
            s=(char)(s-'a'+'A');
        }
        return s==t?true:false;

    }

*/



   /* public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别

        int n = in.nextInt();
        if (n<=2){
            System.out.println("1");
        }else{
            int a = 1;
            int b = 1;
            int c = 0;
            while (n>2){
                c = a+b;
                a=b;
                b=c;
            }
            System.out.println(c);
        }




    }
*/




/*    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        while (in.hasNext()){
            String str = in.nextLine();
            String find = in.nextLine();
            int count = 0;
            for(char i:str.toCharArray()){
                if (String.valueOf(i).equalsIgnoreCase(find.substring(0,1))){
                    count++;
                }
            }
            System.out.println(count);
        }



    }*/

/*
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()){
            int n = in.nextInt();
            int[][] a = new int[n][2*n-1];
            for(int i = 0;i<n;i++){
                for(int j = 0;j<2*n-1;j++){
                    a[i][j] = 0;
                }
            }
            a[0][0]=1;
            for(int i = 1;i<n;i++){
                a[i][0] = a[i][2*i]=1;
                for(int j=1;j<2*i;j++){
                    if (j==1){
                        a[i][j] = a[i-1][j]+a[i-1][j-1];
                    }else{
                        a[i][j] = a[i-1][j]+a[i-1][j-1]+a[i-1][j-2];
                    }
                }
            }

            int k = 0;
            for(;k<2*n-1;k++){
                if (a[n-1][k]%2==0){
                    System.out.println(k+1);
                    break;
                }
            }
            if (k==2*n-1){
                System.out.println("-1");
            }


        }





    }
*/



/*

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        String[] pp = str.split("-");
        String[] p1 = pp[0].split(" ");
        String[] p2 = pp[1].split(" ");
        String p = "34567891JQKA2";

        if (pp[0].equals("joker JOKER") || pp[1].equals("joker JOKER")){
            System.out.println("joker JOKER");
        }else if(p1.length == p2.length){
            if (p.indexOf(p1[0].substring(0,1)) > p.indexOf(p2[0].substring(0,1)) ){
                System.out.println(pp[0]);
            }else{
                System.out.println(pp[1]);
            }
        }else if (p1.length == 4){
            System.out.println(pp[0]);
        }else if(p2.length == 4){
            System.out.println(pp[1]);
        }else {
            System.out.println("ERROR");
        }
    }
*/















}
